九章算法解析|网易面试真题：最优线段覆盖问题深入探讨

描述

在一个数轴上给出n个线段&＃xff0c;问选择不超过k个线段&＃xff0c;使得这k个线段覆盖的数最多。

在线测评地址

样例1

Input:
[(1,2),(2,3),(3,4)]
2
Output: 4
Explanation:
Select the line segment (1,2), (3,4), which can cover the 4 numbers of 1,2,3,4.

样例2

Input:
[(1,2),(2,3),(1,7)]
2
Output: 7
Explanation:
Selecting the line segment (1,7) ,which can cover the 7 numbers of 1,2,3,4,5,6,7.

题解

dp[i][j]dp[i][j]表示用jj个线段覆盖前ii个数的最优答案。先将所有线段按照左端点排序&＃xff0c;对于左端点相同的线段&＃xff0c;取最长的拿来转移。 则有&＃xff1a; dp[i&＃43;1][j]&＃61;max(dp[i][j],dp[i&＃43;1][j])dp[i&＃43;1][j]&＃61;max(dp[i][j],dp[i&＃43;1][j]) dp[i&＃43;num][j&＃43;1]&＃61;max(dp[i][j]&＃43;num,dp[i&＃43;num][j&＃43;1])dp[i&＃43;num][j&＃43;1]&＃61;max(dp[i][j]&＃43;num,dp[i&＃43;num][j&＃43;1])(num为线段长度)

/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start &＃61; start;* this.end &＃61; end;* }* }*/public class Solution {/*** &＃64;param intervals: The intervals* &＃64;param k: The k* &＃64;return: The answer*/class Cmp implements Comparator{&＃64;Overridepublic int compare(Interval a, Interval b){if(a.start &＃61;&＃61; b.start) {return a.end - b.end;}return a.start - b.start;}} public int maximumLineCoverage(List intervals, int k) {// Write your code hereCollections.sort(intervals, new Cmp());int index &＃61; 0;int num &＃61; 0;int maxnum &＃61; 0;int[][] dp &＃61; new int[2005][2005];for (int i &＃61; 0; i 0) {//i加了1&＃xff0c;所以线段长度减1num--;}}return dp[maxnum][k];}
}

更多题解参考